package huffMan;


import java.util.ArrayList;

/*
  __             _   _
 / _|  _   _    (_) (_)   ___
| |_  | | | |   | | | |  / _ \
|  _| | |_| |   | | | | |  __/
|_|    \__,_|  _/ | |_|  \___|
              |__/
 */

/*
测试样例
输入：
8
c a s t i e f g
5 29 7 8 14 23 3 11

输入： state
输出：1110111110111101
*/
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

class Node {
    private int weight;//权值
    private int Parent;//父节点的下标
    private int Lchild;
    private int Rchild;

    public int getLchild() {
        return Lchild;
    }

    public int getParent() {
        return Parent;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public void setParent(int parent) {
        Parent = parent;
    }

    public void setLchild(int lchild) {
        Lchild = lchild;
    }

    public int getRchild() {
        return Rchild;
    }

    public void setRchild(int rchild) {
        Rchild = rchild;
    }

    public Node(int weight) {
        this.weight = weight;
        this.Lchild = 0;
        this.Rchild = 0;
        this.Parent = 0;
    }
    @Override
    public String toString() {
    	return "w="+weight+" p="+Parent+" L="+Lchild+" R="+Rchild;
    }
}
public class HuffManTree{
    private int n;//叶子节点的个数
    private Node[] nodes;
    private char[] datas;
    private HashMap<Character,String> codes;
    public HuffManTree(int[] content) {
    	
		ArrayList<Integer> weightsList = new ArrayList<>(content.length);
		ArrayList<Character> datasList = new ArrayList<>(content.length);
		for(int i = 0; i < content.length; i++) {
			if(content[i] != 0) {
				datasList.add((char)i);
				weightsList.add(content[i]);
			}
		}
		datasList.trimToSize();
		weightsList.trimToSize();
		Character[] Datas = new Character[datasList.size()];
		Integer[] Weights = new Integer[weightsList.size()];
		datasList.toArray(Datas);
		weightsList.toArray(Weights);
		char[] datas = new char[Datas.length];
		int[] weights = new int[Weights.length];
		for(int i = 0; i < Datas.length;i++) {
			datas[i] = Datas[i];
			weights[i] = Weights[i];
		}
		NewHuffManTree(datas, weights);
    }

	public HuffManTree(char [] datas,int[] weights){
		NewHuffManTree(datas, weights);
    }
	private void NewHuffManTree(char[] datas,int[] weights) {
        this.n = weights.length;
        this.datas = datas;
        nodes = new Node[2*n];
        //哈夫曼树共有2*n-1个节点  这里多开一个节点是因为0号单元不直接使用
        codes = new HashMap<>();
        InitHuffManTree(weights);
        GenerateHuffManCode(datas);
	}
	public String Encode(byte[] datas) {
		StringBuilder code = new StringBuilder();
        for(byte ch : datas){
        	code.append(getCodes().get((char)ch));
        }
        return code.toString(); 
	}
    public String Encode(String string){
    	byte[] datas = string.getBytes();
    	return Encode(datas);
    }
    public String Decode(String code){
    	char[] codes = code.toCharArray();
    	StringBuilder s = new StringBuilder();
    	int i = 2*n-1;
    	for(char ch : codes){
    		if(ch == '0'){
    			i = nodes[i].getLchild();
    		}else {
				i = nodes[i].getRchild();
			}
    		if(nodes[i].getLchild()==0) {
    			s.append(datas[i-1]);
    			i = 2*n-1;
    		}
    	}
    	return s.toString();
    }
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        System.out.print("请输入字符个数：");
        int n = s.nextInt();
        System.out.print("请依次输入字符：");
        char[] datas = new char[n];
        int[] weights = new int[n];
        for (int i = 0; i < n; i++){
            datas[i] = s.next().charAt(0);
        }
        System.out.print("请依次输入权值：");
        for (int i = 0; i < n; i++){
            weights[i] = s.nextInt();
        }
        s.nextLine();
        HuffManTree h = new HuffManTree(datas,weights);
        System.out.println(h.getCodes());
        System.out.print("请输入要编码的字符串：");      
        String code = h.Encode(s.nextLine());
        System.out.println(code);
        System.out.println(h.Decode(code));
        s.close();
    }
    public HashMap<Character, String> getCodes() {
        return codes;
    }

    private  void InitHuffManTree(int[] weights){
    	final int Maxint = (int)Math.pow(2, 32);
    	nodes[0] = new Node(Maxint);
        for(int i = 1; i < n+1; i++){
            nodes[i] = new Node(weights[i-1]);
        }
        for(int i = n+1; i < 2*n; i++){
            nodes[i] = new Node(0);
        }
        int[] min;
        for(int i = n+1;i < 2*n; i++){
            min = select(nodes ,i-1);
            nodes[i].setWeight(nodes[min[0]].getWeight()+nodes[min[1]].getWeight());
            nodes[i].setLchild(min[0]);
            if(min[0] != min[1]) nodes[i].setRchild(min[1]);
            nodes[min[0]].setParent(i);
            nodes[min[1]].setParent(i);
        }
        /*
        for(Node n : nodes) {
            System.out.println(n);
        }
        */
    }
    private void GenerateHuffManCode(char[] datas){
        char[] code = new char[n];
        for(int i = 0; i<datas.length; i++){ ;
            int start = code.length;
            int CurNode = i+1 ,Parent = nodes[CurNode].getParent();
            while(Parent != 0){
                if(nodes[Parent].getLchild() == CurNode){
                    code[--start] = '0';
                }else if(nodes[Parent].getRchild() == CurNode){
                    code[--start] = '1';
                }
                CurNode = Parent;
                Parent = nodes[CurNode].getParent();
            }
            //System.out.println(new String(code));
            String scode  = String.valueOf(Arrays.copyOfRange(code,start,code.length));
            codes.put(datas[i],scode);
        }
    }

	private int[] select(Node[] nodes, int n) {
		// 在nodes的前n项中找到双亲节点为0 且权值最小的两项 返回
		int[] min = new int[] { 0, 0 };
		for (int i = 1; i <= n; i++) {
			if (nodes[i].getParent() != 0)
				continue;
			if (nodes[i].getWeight() < nodes[min[0]].getWeight()) {
				min[1] = min[0];
				min[0] = i;
			} else if (nodes[i].getWeight() < nodes[min[1]].getWeight()) {
				min[1] = i;
			}
		}
		if(min[0] > min[1]) {
			int temp = min[0];
			min[0] = min[1];
			min[1] = temp;
		}
		return min;
	}

}